2307. Сумма

 

Задан масив из n элементов. Найдите сумму чисел на заданных интервалах.

 

Вход. Первая строка содержит два целых числа n и k (1 ≤ n ≤ 105, 0 ≤ k ≤ 105) – количество элементов в массиве и количество запросов. Следующие k строк содержат запросы двух типов:

·        A l r x – присвоить значение x каждому элементу на позициях от l до r (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 109)

·        Q l r – найти сумму элементов массива на позициях от l до r (1 ≤ l ≤ r ≤ n)

Изначально массив заполнен нулями.

 

Выход. Для каждого запроса вида Q l r выведите сумму чисел на этом отрезке.

 

Пример входа

Пример выхода

5 9

A 2 3 2

A 3 5 1

A 4 5 2

Q 1 3

Q 2 2

Q 3 4

Q 4 5

Q 5 5

Q 1 5

3

2

3

4

2

7

 

 

РЕШЕНИЕ

структуры данных – дерево отрезков

 

Анализ алгоритма

Для решения задачи необходимо реализовать дерево отрезков, поддерживающее групповые операции – присваивание и суммирование.

В каждом узле дерева в переменной add хранится значение, присвоенное всем элементам отрезка, соответствующего данному узлу. Если вершина дерева соответствует отрезку [l; r], то сумма чисел на этом отрезке равна add * (r – l + 1).

При выполнении операций присваивания и суммирования, в процессе спуска по дереву от корня к листьям, значение add в каждой вершине необходимо проталкивать на следующий уровень дерева.

При выполнении операции присваивания предыдущие значения сумм в дочерних вершинах s1 и s2, а также значения отложенных присваиваний a1 и a2, теряются.

При построении дерева отрезков переменную add в каждой вершине инициализируем значением, которое никогда не будет присваиваться элементам отрезка (например, -1).

 

Реализация алгоритма

Дерево отрезков хранится в виде массива SegTree, элементы которого имеют тип node. Каждая вершина дерева соответствует некоторому отрезку массива и хранит информацию об этом отрезке.

Структура node содержит два поля:

·        sum – сумму элементов на соответствующем отрезке;

·        add – значение отложенного присваивания (lazy propagation).

Конструктор вызывается автоматически при создании каждой вершины дерева:

·        sum инициализируется нулём, так как на этапе построения в вершине ещё не накоплена информация о значениях элементов;

·        add инициализируется значением -1, которое используется как специальный маркер и означает отсутствие отложенного присваивания. Предполагается, что это значение никогда не будет реально присваиваться элементам массива.

 

struct node

{

  long long sum, add;

  node() : sum(0), add(-1) {}

};

vector<node> SegTree;

 

Функция Push выполняет проталкивание значения add из вершины v в сыновья. Если add ≠ -1, то это значение необходимо протолкнуть на один уровень ниже по дереву. После завершения проталкивания значение add в вершине v устанавливаем равным -1.

 

void Push(int v, int lpos, int mid, int rpos)

{

 

Если add = -1, то в вершине v отсутствует отложенная операция.

 

  if (SegTree[v].add == -1) return;

 

Выполняем пересчет значений add и sum в сыновьях вершины v.

 

  SegTree[2*v].add = SegTree[v].add;

  SegTree[2*v].sum = (mid - lpos + 1) * SegTree[v].add;

  SegTree[2*v+1].add = SegTree[v].add;

  SegTree[2*v+1].sum = (rpos - mid) * SegTree[v].add;

 

После завершения проталкивания устанавливаем add = -1 в вершине v.

 

  SegTree[v].add = -1;

}

 

Функция SetValue устанавливает все элементы отрезка [left; right] равными val. Вершине v соответствует отрезок [lpos; rpos].

 

void SetValue(int v, int lpos, int rpos, int left, int right, int val)

{

    if (left > right) return;

 

Если [left; right] соответствует отрезку [lpos; rpos], который хранится в вершине дерева, то в этой вершине присваиваем переменным add и sum соответствующие значения.

 

  if ((lpos == left) && (rpos == right))

  {

 

    SegTree[v].add = val;

    SegTree[v].sum = (long long)(right - left + 1) * val;

    return;

  }

 

Находим середину отрезка mid = (lpos + rpos) / 2.

 

  int mid = (lpos + rpos) / 2;

 

Проведем проталкивание, если add не равно -1.

 

  Push(v, lpos, mid, rpos);

 

Рекурсивно обрабатываем левого и правого сына текущей вершины дерева отрезков.

 

  SetValue(2*v, lpos, mid, left, min(mid, right), val);

  SetValue(2*v+1, mid+1, rpos, max(left, mid+1), right, val);

 

Пересчитываем значение суммы в вершине v через значения сумм ее детей.

 

  SegTree[v].sum = SegTree[2*v].sum + SegTree[2*v+1].sum;

}

 

Функция Summa возвращает сумму элементов на отрезке [left; right].

Вершине v соответствует отрезок [lpos; rpos].

 

long long Summa(int v, int lpos, int rpos, int left, int right)

{

  if (left > right) return 0;

 

Если [left; right] совпадает с отрезком [lpos; rpos], который хранится в вершине v дерева, возвращаем значение суммы в этой вершине.

 

  if ((lpos == left) && (rpos == right))

    return SegTree[v].sum;

 

Находим середину отрезка mid = (lpos + rpos) / 2.

 

  int mid = (lpos + rpos) / 2;

 

Проведем проталкивание, если add не равно -1.

 

  Push(v, lpos, mid, rpos);

 

Разбиваем отрезок [lpos; rpos] на два подотрезка: [lpos; mid] и [mid + 1; rpos]. Рекурсивно вычисляем суммы на этих подотрезках и складываем полученные значения.

 

  return Summa(2*v, lpos, mid, left, min(mid, right)) +

         Summa(2*v+1, mid+1, rpos, max(left, mid+1), right);

}

 

Основная часть программы. Читаем входные данные. Инициализируем дерево отрезков.

 

cin >> n >> k;

SegTree.resize(4 * n);

 

Обрабатываем k запросов. В зависимости от типа запроса выполняем либо групповое присваивание, либо вычисление суммы на заданном отрезке.

 

while (k--)

{

  cin >> c;

  if (c == 'A')

  {

    cin >> l >> r >> x;

    SetValue(1, 1, n, l, r, x);

  }

  else

  {

    cin >> l >> r;

    cout << Summa(1, 1, n, l, r) << endl;

  }

}

 

Реализация с помощью класса

 

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

 

class SegmentTree

{

public:

  const static int NONE_ASSIGN = -1;

  vector<long long> Summa, Add;

  int len;

 

  SegmentTree(int n)

  {

    len = n;

    Summa.resize(4*n);

    Add.resize(4* n);

    BuildZeroTree(1, 1, len);

  }

 

  void BuildZeroTree(int v, int lpos, int rpos)

  {

    if (lpos == rpos)

    {

      Summa[v] = 0;

      Add[v] = NONE_ASSIGN;

    }

    else

    {

      int mid = (lpos + rpos) / 2;

      BuildZeroTree(2*v, lpos, mid);

      BuildZeroTree(2*v+1, mid + 1, rpos);

 

      Summa[v] = Summa[2*v] + Summa[2*v+1];

      Add[v] = NONE_ASSIGN;

    }

  }

 

  void Push(int v, int lpos, int mid, int rpos)

  {

    if (Add[v] == NONE_ASSIGN) return;

 

    Add[2*v] = Add[v];

    Summa[2*v] = (mid - lpos + 1) * Add[v];

    Add[2*v+1] = Add[v];

    Summa[2*v+1] = (rpos - mid) * Add[v];

 

    Add[v] = NONE_ASSIGN;

  }

 

  void SetValue(int left, int right, int val)

  {

    SetValue(1, 1, len, left, right, val);

  }

 

  void SetValue(int v, int lpos, int rpos,

                int left, int right, int val)

  {

    if (left > right) return;

    if ((lpos == left) && (rpos == right))

    {

      Add[v] = val;

      Summa[v] = (long long)(right - left + 1) * val;

      return;

    }

 

    int mid = (lpos + rpos) / 2;

    Push(v, lpos, mid, rpos);

 

    SetValue(2*v, lpos, mid, left, min(mid, right), val);

    SetValue(2*v+1, mid+1, rpos, max(left, mid + 1), right, val);

 

    Summa[v] = Summa[2*v] + Summa[2*v+1];

  }

 

  long long Sum(int left, int right)

  {

    return Sum(1, 1, len, left, right);

  }

 

  long long Sum(int v, int lpos, int rpos, int left, int right)

  {

    if (left > right) return 0;

    if ((lpos == left) && (rpos == right)) return Summa[v];

 

    int mid = (lpos + rpos) / 2;

    Push(v, lpos, mid, rpos);

 

    return Sum(2*v, lpos, mid, left, min(mid, right)) +

           Sum(2*v+1, mid+1, rpos, max(left, mid + 1), right);

  }

};

 

int n, k, l, r, x;

char c;

 

int main(void)

{

  scanf("%d %d\n", &n, &k);

  SegmentTree s(n);

  while (k--)

  {

    scanf("%c ", &c);

    if (c == 'A')

    {

      scanf("%d %d %d\n", &l, &r, &x);

      s.SetValue(l, r, x);

    }

    else

    {

      scanf("%d %d\n", &l, &r);

      printf("%lld\n", s.Sum(l, r));

    }

  }

  return 0;

}

 

Реализация дерева отрезков на указателях

 

Из элементов вектора v функция build создает дерево отрезков.

 

SegmentTree *build(vector<long long> &v, int L, int R)

{

  if (L == R)

  {

    SegmentTree *New = new SegmentTree ;

    New->summa = v[L]; New->add = -1;

    New->Left = New->Right = NULL;

    New->LeftPos = New->RightPos = L;

    return New;

  }

 

  int m = (L + R) / 2;

  SegmentTree *Left =  build(v,L,m);

  SegmentTree *Right = build(v,m+1,R);

 

  SegmentTree *Tree = new SegmentTree;

  Tree->Left = Left; Tree->Right = Right;

 

  Tree->summa = Left->summa + Right->summa;

  Tree->LeftPos = Left->LeftPos;

  Tree->RightPos = Right->RightPos;

  Tree->add = -1;

  return Tree;

}

 

Функция SetValue присваивает значение value всем элементам на отрезке [L; R].

 

void SetValue(SegmentTree *&tree, int L, int R, long long value)

{

  if (L < tree->LeftPos) L = tree->LeftPos;

  if (R > tree->RightPos) R = tree->RightPos;

  if (L > R) return;

 

Если [L; R] соответствует отрезку, который хранится в вершине дерева [LeftPos; RightPos], то присваиваем в текущей вершине дерева переменным add и summa соответствующие значения.

 

  if ((tree->LeftPos == L) && (tree->RightPos == R))

  {

    tree->add = value;

    tree->summa = value * (R - L + 1);

    return;

  }

 

Если значение tree->add установлено (не равно -1), то следует протолкнуть его на уровень ниже. При этом следует пересчитать значение суммы в дочерних вершинах tree->Left->summa и tree->Right->summa.

 

  if (tree->add != -1)

  {

    if (tree->Left != NULL)

      tree->Left->add = tree->add,

      tree->Left->summa = tree->add *

                          (tree->Left->RightPos - tree->Left->LeftPos + 1);

    if (tree->Right != NULL)

      tree->Right->add = tree->add,

      tree->Right->summa = tree->add *

                           (tree->Right->RightPos - tree->Right->LeftPos + 1);

    tree->add = -1;

  }

 

Рекурсивно модифицируем левое и правое поддерево. Пересчитываем значение суммы в текущей вершине дерева.

 

  SetValue(tree->Left,L,R,value);

  SetValue(tree->Right,L,R,value);

  tree->summa = tree->Left->summa + tree->Right->summa;

}

 

Функция Summa возвращает значение суммы на отрезке [L; R].

 

long long Summa(SegmentTree *&tree, int L, int R)

{

  if (L < tree->LeftPos) L = tree->LeftPos;

  if (R > tree->RightPos) R = tree->RightPos;

  if (L > R) return 0;

 

Если [L; R] соответствует отрезку в вершине дерева, то возвращаем хранящееся в нем значение суммы.

 

  if ((tree->LeftPos == L) && (tree->RightPos == R))

    return tree->summa;

 

Производим проталкивание значения add на уровень ниже с пересчетом суммы для дочерних узлов.

 

  if (tree->add != -1)

  {

    if (tree->Left != NULL)

      tree->Left->add = tree->add,

      tree->Left->summa = tree->add *

                          (tree->Left->RightPos - tree->Left->LeftPos + 1);

    if (tree->Right != NULL)

      tree->Right->add = tree->add,

      tree->Right->summa = tree->add *

                           (tree->Right->RightPos - tree->Right->LeftPos + 1);

    tree->add = -1;

  }

 

Возвращаем искомую сумму, извлекая информацию из левого и правого поддерева.

 

  return Summa(tree->Left,L,R) + Summa(tree->Right,L,R);

}

 

Основная часть программы. Строим дерево отрезков Tree, содержащее изначально все нули. В зависимости от входного запроса совершаем либо групповое присваивание, либо вычисление суммы на отрезке.

 

scanf("%d %d\n",&n,&k);

Tree = build(v,0,n); 

while(k--)

{

  scanf("%c ",&c);

  if (c == 'A')

  {

    scanf("%d %d %d\n",&l,&r,&x);

    SetValue(Tree,l,r,x);

  }

  else

  {

    scanf("%d %d\n",&l,&r);

    printf("%lld\n",Summa(Tree,l,r));

  }

}